package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-15 19:20
 * @description: Functions of this class is
 *官方做法：
 * class Solution {
 *     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 *        ListNode head=null;
 *        ListNode tail=null;
 *        int carry=0;//定义一个进位标志,初始值位为0
 *        while(l1!=null||l2!=null){
 *            int tot= l1==null?0:l1.val;
 *            tot+= l2==null? 0:l2.val;
 *            int sum=tot+carry;//记录当前两链表加起来的总值
 *             carry=sum/10;
 *            if(head==null){
 *                //说明是头结点
 *                head=tail=new ListNode(sum%10);//这里不要用-，因为有可能是负数，不一定都是正数
 *            }
 *            else{
 *                //说明不是头结点，直接插入尾部
 *                tail.next=new ListNode(sum%10);
 *                tail=tail.next;//往下走
 *            }
 *            if(l1!=null){
 *                l1=l1.next;
 *            }
 *            if(l2!=null){
 *                l2=l2.next;
 *            }
 *        }
 *        if(carry>0){//最后这个进位一定不要忘，不然就过不去
 *            tail.next=new ListNode(carry);
 *        }
 *        return head;
 *     }
 * }
 *
 **/
public class NoNo两数相加 {
    public static void main(String args[]){

        /**
         * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户，内存消耗：8.4 MB, 在所有 Java 提交中击败了80.45%的用户
         *
         *
         * 由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
         * 我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2
         * 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0
         * 此外，如果链表遍历结束后，有carry>0， 还需要在答案链表的后面附加一个节点，节点的值为carry。
         * 自我消化题解：速度100%
         * class Solution {
         *     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
         *         ListNode head=new ListNode();
         *         ListNode tail=head;
         *         int carry=0;
         *         while(l1!=null||l2!=null||carry!=0){//循环这里直接判断是否还有进位，有的话还能再进入循环
         *             ListNode p=new ListNode();
         *             p.val=(l1==null)?carry:l1.val+carry;
         *             p.val=(l2==null)?p.val:p.val+l2.val;
         *             carry=(p.val>=10)?1:0;
         *             p.val%=10;
         *             l1=(l1==null)?l1:l1.next;
         *             l2=(l2==null)?l2:l2.next;
         *             tail.next=p;
         *             tail=p;
         *         }
         *         return head.next;
         *     }
         * }
         */
    }
}